1. Field of the Invention
The present invention generally relates to the link state routing protocol. More specifically, the present invention provides techniques and mechanisms for improving the link state routing protocol to prevent formation of transient loops.
2. Description of Related Art
Link state routing is a protocol that allows a node in a network to determine network topology by sharing information about transmission cost to each of its neighboring nodes. Link state routing packets are transmitted to neighbors and link state routing packets are received from neighbors. With the shared link state information, the least expensive paths to various destinations can be determined.
In broadcast or shared multicast networks, link state routing allows a network to generate a broadcast or shared multicast tree. However, transient loops can sometimes arise when network topology changes because neighboring nodes may not be forwarding transmissions using the same generated network topology. Some data may be continuously transmitted in loops without ever reaching their assigned destinations. A variety of techniques have been used to address transient loops.
In conventional Internet Protocol networks, time to live (TTL) is a parameter used to drop packets after an expiration time period. If a packet is trapped in a transient loop, the packet is merely dropped after a period of time. However, transient loops in broadcast and multicast traffic cause delivery of multiple copies of the same looped packets to destinations. Furthermore, some fabrics and networks do not use a TTL field.
The Spanning Tree Protocol (802.1d) waits for 15 seconds before forwarding data along a newly generated link to make sure that a change is propagated to the rest of the network during topology changes. However, the traditional spanning tree protocol has slow convergence times. Rapid Spanning Tree (802.1w) uses proposal agreement logic to ensure there are no transient loops. However, Rapid Spanning Tree can be inefficient in certain network topologies such as chain topologies. Furthermore, Rapid Spanning Tree has a well known count to infinity problem.
The Enhanced Interior Gateway Routing Protocol (EIGRP) is a layer 3 distance vector routing protocol that uses dual algorithms to provide that route recomputation occurs in the right order in the network to prevent transient loops. However, EIGRP is limited to layer 3 routing.
U.S. Pat. No. 5,265,092 provides a loop free link state protocol by ensuring that packets are dropped during unsteady state. New packets called ready link state packets (LSP) are used to inform neighbors that a LSR has been used in route computation. Two sets of LSR data are maintained. One is the set of most up to date LSR data and the second is the intelligent set including LSR data not yet committed. Routes are computed based on both the current set and the intelligent set to decide which destination's traffic should be dropped. However, maintenance of both an updated LSR data set and an intelligent LSR data set has extra complexity and overhead.
Current implementations for preventing transient loops using link state routing are limited or are too complicated. Consequently, the techniques of the present invention provide mechanisms for determining transient loop free broadcast and shared multicast trees with simple change to link state routing.